package ReviewAlgorithms.sort;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class FrequencySort {

    public static void main(String[] args) {
        String str = "tree";
        System.out.println(frequencySort(str));
    }
    public static String frequencySort(String s) {
        if (s == null || s.length() < 1){
            return s;
        }
        Map<Character,Integer> frequencyMap = new HashMap<>();
        Queue<Character> characterQueue = new PriorityQueue<>((o1 , o2) -> frequencyMap.get(o2) - frequencyMap.get(o1));
        for (int i = 0; i < s.length(); i++) {
            frequencyMap.put(s.charAt(i),frequencyMap.getOrDefault(s.charAt(i),0) + 1);
        }
        characterQueue.addAll(frequencyMap.keySet());
        StringBuilder stringBuilder = new StringBuilder(s.length());
        while (!characterQueue.isEmpty()) {
            char temp = characterQueue.poll();
            for (int i = 0; i < frequencyMap.get(temp); i++) {
                stringBuilder.append(temp);
            }
        }

        return stringBuilder.toString();
    }
}
